package set;

public class NextPermutation31 {
    public void nextPermutation(int[] n) {
        int p = -1;
        // 从右向左找到第一个左侧小于右侧的位置, 左侧记为p;
        for (int i = n.length-2; i >= 0; i--) {
            if (n[i] < n[i+1]) {
                p = i;
                break;
            }
        }

        if (p == -1) {
            // 已经是最大了
            reverse(n, 0, n.length-1);
            return;
        }

        // 从右向左找到第一个大于n[p]的下标，记为r; 一定有r>p;
        int r = -1;
        for (int i = n.length-1; i > p; i--) {
            if (n[i] > n[p]) {
                r = i;
                break;
            }
        }
        swap(n, p, r);
        if (p < n.length-1) {
            reverse(n, p+1, n.length-1);
        }
    }

    public void swap(int[] n, int i, int j) {
        int t = n[i];
        n[i] = n[j];
        n[j] = t;
    }

    // [start, end]
    public void reverse(int[] n, int start, int end) {
        while (start < end) {
            swap(n, start, end);
            start++;
            end--;
        }
    }
}
